/**
 * @version Create on 2012-10-31
 * @author Yinzi Chen
 */
public class ConvertSortedListToBST {

	class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode buildTree(ListNode head) {
		if (head == null)
			return null;
		ListNode mid = head;
		ListNode r = head;
		ListNode pre = null;
		while (r.next != null) {
			r = r.next;
			pre = mid;
			mid = mid.next;
			if (r.next != null)
				r = r.next;
		}
		TreeNode root = new TreeNode(mid.val);
		if (mid != head) {
			pre.next = null;
			root.left = buildTree(head);
		}
		root.right = buildTree(mid.next);
		return root;
	}

	public TreeNode sortedListToBST(ListNode head) {
		return buildTree(head);
	}

	public static void main(String[] args) {

	}

}
